๋ฌธ์
Programmers - ๋ฉ๋ด ๋ฆฌ๋ด์ผ
๐ Logic
// map์ ํด๋น ์กฐํฉ์ด ์๋ค๋ฉด, count๋ ๊ทธ ์กฐํฉ์ ๋น๋ ์, ๊ทธ๋ ์ง ์๋ค๋ฉด 0
int count = 0;
if (menuComb.containsKey(str))
count = menuComb.get(str);
// ํ์ฌ ํด๋น ์กฐํฉ์ ์ถ๊ฐํ ๊ฒ์ด๋ฏ๋ก count๋ฅผ ์ฆ๊ฐ
count++;
// ํด๋น ์กฐํฉ์ด ์ด๋ฏธ ์์๊ณ , ํด๋น ์กฐํฉ(๋ฉ๋ด ๊ตฌ์ฑ)์ด ์ํ ์ฝ์ค ์ค ์ต๋ ๋น๋๋ณด๋ค ๋น๋๊ฐ ํฌ๋ค๋ฉด ์ต์ ํ
if (count != 1 && courseMaxCount.get(str.length()) < count)
courseMaxCount.put(str.length(), count);
menuComb.put(str, count);
- ๋ฉ๋ด ๊ตฌ์ฑ ๊ธธ์ด๋ณ ์ต๋ ๋น๋์๋ฅผ ์ ์ฅํ๋
map์ ์ต์ ํํ๋ ๊ณผ์
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
// ๋ชจ๋ ๋ฉ๋ด ์กฐํฉ์ ์ ์ฅ
static Map<String, Integer> menuComb = new HashMap<>();
// ๊ฐ course๋ณ ์ต๋ ๋ฉ๋ด ์๋ฅผ ์ ์ฅ
static Map<Integer, Integer> courseMaxCount = new HashMap<>();
// ์ต์ ์ฝ์ค ์๋ฆฌ ์ = course[0]
static int minCombCount;
public String[] solution(String[] orders, int[] course) {
// ๊ฐ ์ฝ์ค๋ณ ์๋ฆฌ ์์ ๋ํ ์ต๋๊ฐ์ ์ ์ฅํ map ์ด๊ธฐํ
for (int c : course) courseMaxCount.put(c, 0);
minCombCount = course[0];
// ๊ฐ๋ฅํ ๋ชจ๋ ์กฐํฉ์ ์์ฑํด์ menuComb์ ์ถ๊ฐ
for (String order : orders) {
boolean[] visited = new boolean[order.length()];
for (int c : course)
if (order.length() >= c)
makeComb(order, visited, 0, order.length(), c);
}
ArrayList<String> answer = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : courseMaxCount.entrySet())
// ์ต๋ ๋น๋๋ฅผ ๊ฐ์ง๋ ๋ฉ๋ด result์ ์ถ๊ฐ
for (Map.Entry<String, Integer> menu : menuComb.entrySet())
if (entry.getKey() == menu.getKey().length() && entry.getValue() == menu.getValue())
answer.add(menu.getKey());
Collections.sort(answer);
return answer.toArray(String[]::new);
}
private static void makeComb(String order, boolean[] visited, int start, int n, int r) {
// ์ฃผ์ด์ง ์๋ฆฌ ์๋งํผ์ ์กฐํฉ์ด ๋ง๋ค์ด์ง ๊ฒฝ์ฐ, map์ ์ถ๊ฐ
if (r == 0) {
put(order, visited, n);
return;
}
for (int i = start; i < n; i++) {
visited[i] = true;
makeComb(order, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
private static void put(String order, boolean[] visited, int n) {
// Map์ ๋ฃ์ ๋ฉ๋ด ์กฐํฉ ์์ฑ
StringBuilder sb = new StringBuilder();
for (int i = 0; i < order.length(); i++)
if (visited[i]) sb.append(order.charAt(i));
// ์ต์ ์ฝ์ค ์๋ฆฌ ์๋ณด๋ค ์์ ๊ฒฝ์ฐ๋ ํจ์ค
if (sb.length() < minCombCount) return;
// ๋ฉ๋ด ์กฐํฉ ์ฌ์ ์ ์ ๋ ฌ, AB์ BA๋ ๊ฐ์ ๋ฉ๋ด ์กฐํฉ์ด๋ฏ๋ก
char[] chars = sb.toString().toCharArray();
Arrays.sort(chars);
String str = new String(chars);
// map์ ํด๋น ์กฐํฉ์ด ์๋ค๋ฉด, count๋ ๊ทธ ์กฐํฉ์ ๋น๋ ์, ๊ทธ๋ ์ง ์๋ค๋ฉด 0
int count = 0;
if (menuComb.containsKey(str))
count = menuComb.get(str);
// ํ์ฌ ํด๋น ์กฐํฉ์ ์ถ๊ฐํ ๊ฒ์ด๋ฏ๋ก count๋ฅผ ์ฆ๊ฐ
count++;
// ํด๋น ์กฐํฉ์ด ์ด๋ฏธ ์์๊ณ , ํด๋น ์กฐํฉ(๋ฉ๋ด ๊ตฌ์ฑ)์ด ์ํ ์ฝ์ค ์ค ์ต๋ ๋น๋๋ณด๋ค ๋น๋๊ฐ ํฌ๋ค๋ฉด ์ต์ ํ
if (count != 1 && courseMaxCount.get(str.length()) < count)
courseMaxCount.put(str.length(), count);
menuComb.put(str, count);
}
}
โ๏ธ Review
- ๊ฐ๋ฅํ ๋ชจ๋ ์กฐํฉ์ ๊ตฌํ๋ ๊ฒ์ด ๊ฐ์ฅ ๊ด๊ฑด์ด์๋ค. ์ดํ ๊ตฌํ์ ์ ๋ ฌ์ ์ ํ์ฉํ๋ฉด ๋๋ ๋ฌธ์ ์๋ค.
- ์ฒ์์๋ ์กฐํฉ์ ๋ง๋ค๊ณ , ๊ฐ ์ฝ์ค ์๋ฆฌ๋ณ ๋ฉ๋ด ์์ ์ต๋ ๋น๋๋ฅผ ๊ตฌํ๊ณ , ๊ทธ ๋น๋๋ฅผ ๊ฐ์ง๋ ๋ฉ๋ด ๊ตฌ์ฑ์ ์ถ๋ ฅํ๋๋ก ํ๋ค๊ฐ, ์กฐํฉ์ ๋ง๋ค๊ณ
map์ ์ถ๊ฐํ ๋, ๋ฉ๋ด ๊ตฌ์ฑ ๊ธธ์ด๋ณ ์ต๋ ๋น๋๋ฅผ ์ ์ฅํ๋map์ ๋์ด ์ด๋ฅผ ์ฌ์ฉํ๋๋ก ๋ณ๊ฒฝํด๋ณด์๋ค.